#include <stdio.h>

void quick_sort(int arr[], int left, int right)
{ // 定义基准值
    int base = arr[left];

    // 终止递归的条件
    while (left >= right) // 这里必须写大于等于,有可能在快排中左右子数组为空
    {                     // 子数组长度为1 或者为空
        return;
    }
    int i = left; // 定义两个哨兵
    int j = right;
    // 大的循环哨兵碰面循环结束
    while (i < j)
    {
        // 循环 j 哨兵, 找小值的哨兵必须先走
        // j哨兵从右向左走（<--）, 右边存放大值的, j哨兵工作发现异常(专找小于基准数的值)
        while (i < j && arr[j] >= base) // i < j 避免哨兵走过他的巡逻范围
        {
            j--;
        }
        // i哨兵从左向右走, 左边存放小值的, i哨兵工作发现异常(专找大于基准数的值)
        while (i < j && arr[i] <= base)
        {
            i++;
        }
        // 双放交换异常元素
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // 哨兵碰面之后所有比 base小的数都在 ij碰面位置左边, base大的数都在 ij碰面位置右边
    // 上面循环j先走 ij停的位置也是小于base的值
    // 接下来就把基准值移动到 ij 碰面的位置, 把ij碰面位置的小值与base交换
    arr[left] = arr[i];
    arr[i] = base;
    // 分出了两个子数组, 这两个子数组使用递归此方法,快排子数组
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

int main(int argc, char const *argv[])
{
    int arr[] = {1, 4, 5, 7, 9, 6, 2, 3, 8};
    int len = sizeof(arr) / sizeof(int);

    quick_sort(arr, 0, len - 1);

    for (int i = 0; i < len; i++)
    {
        printf("%d ", arr[i]);
    }

    printf("\n");

    return 0;
}
